package com.berchen.算法.分治算法;

/**
 * 汉罗塔游戏
 *
 * 当一个塔的时候 直接从a->c
 * 当有多个塔的时候 看成是两个塔
 *  将上面的所有塔 从a->b
 *  将最下面的一个塔 从a->c
 *  将b塔上面的所有塔 从b->c
 */
public class HanRota {

    public static void main(String[] args){

        hanRota(64,'A','B','C');
    }

    /**
     *
     * @param num 一共有多少个塔需要移动
     * @param a     起始柱子
     * @param b     中间柱子
     * @param c     目标柱子
     */
    public static void hanRota(int num,char a ,char b ,char c){
        if(num==1){
            System.out.println("第 "+num+" 个塔，从 "+a+" -> "+c);
        }else {
            // 1. 将上面num-1个塔 从a->b
            hanRota(num-1,a,c,b);
            // 2. 将num 从 a->c
            System.out.println("第 "+num+" 个塔，从 "+a+" -> "+c);
            // 3. 将b柱上的所有塔 b->c
            hanRota(num-1,b,a,c);
        }
    }

}

